import java.awt.image.AreaAveragingScaleFilter;
import java.util.Arrays;

public class TestDemo {


    //归并排序延申问题
    /*
    public static int merge(int[] array, int l, int mid, int r) {
        int p1 = l, p2 = mid + 1, i = 0, res = 0;
        int[] help = new int[r - l + 1];
        while ((p1 <= mid) && (p2 <= r)) {
            res += array[p1] < array[p2] ? (r - p2 + 1)*array[p1] : 0;
            help[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
        }
        while (p1 <= mid) {
            help[i++] = array[p1++];
        }
        while (p2 <= r) {
            help[i++] = array[p2++];
        }
        for(i = 0;i < help.length;i++) {
            array[l + i] = help[i];
        }
        return res;
    }

    public static int process(int[] array, int l, int r) {
        if (l == r) {
            return 0;

        }
        int mid = l + ((r - l)>>>1);
        return process(array, l, mid) +
                process(array, mid + 1, r) +
                merge(array, l, mid, r);
    }

    public static int smallSum(int[] array) {
        return process(array,0,array.length-1);
    }

    public static void main(String[] args) {
        int[] array = {1,3,4,2,5};
        int ret = smallSum(array);
        System.out.println(ret);
    }
    */

    //荷兰国旗

    /*
    public static void swap(int[] arr, int p1, int p2) {

        int t = arr[p1];
        arr[p1] = arr[p2];
        arr[p2] = t;
    }

    public static void process(int[] arr, int num) {
        int p1 = -1,p2 = 0;
        while (p2 < arr.length) {
            if (arr[p2] <= num) {
                swap(arr, p1+1, p2);
                p1++;
                p2++;
            } else {
                p2++;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,2,5,4,7,6,8,10,5,1,3};
        process(arr,5);
        System.out.println(Arrays.toString(arr));
    }
    */

    /*public static void swap(int[] arr, int p1, int p2) {
        int t = arr[p1];
        arr[p1] = arr[p2];
        arr[p2] = t;
    }

    public static void process(int[] arr, int num) {
        int p1 = -1, p2 = arr.length, i = 0;
        while(i < p2) {
            if (arr[i] < num) {
                swap(arr, p1 +1, i);
                i++;
                p1++;

            } else if(arr[i] > num) {
                swap(arr,p2-1,i);
                p2--;

            } else {
                i++;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,5,4,5,7,2,8,10,5,3,6,7};
        process(arr,5);
        System.out.println(Arrays.toString(arr));
    }
     */

    /*public static int[] partition(int[] arr, int l, int r) {
        int less =  l - 1;//联想之前写的p1 = -1，p2 = arr.length
        int more = r;
        while (l < more) { //l代表当前位置，arr[r]代表基准数
            if (arr[l] < arr[r]) {//小于基准数，把边界右边的数与当前位置的数交换，边界扩张，当前位置往后走
                swap(arr, less + 1, l);
                less++;
                l++;

            } else if(arr[l] > arr[r]) {//大于基准数，交换，边界扩张，l不变
                swap(arr,more - 1,l);
                more--;
            } else {
                l++;
            }
        }
        swap(arr,more,r);//归位
        return new int[]{less + 1,more};//返回已经找到的边界
    }

    public static void swap(int[] arr, int p, int q) {
        int t = arr[p];
        arr[p] = arr[q];
        arr[q] = t;
    }

    public static void quickSort(int[] arr, int l, int r) {
        if (l < r) {
            swap(arr, l + (int)(Math.random()*(r - l + 1)), r);//随机取一个值，与最后一个交换做基准
            int[] p = partition(arr, l, r);//做pratition取边界
            quickSort(arr, l, p[0] - 1);
            quickSort(arr, p[1] + 1, r);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,5,4,3,5,1,7,10,2,6};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

     */

    /*public static int[] partition(int[] arr, int l, int r) {
        int less = l - 1;
        int more = r;
        while (l < more) {
            if (arr[l] < arr[r]) {
                swap(arr, less + 1 ,l);
                less++;
                l++;

            } else if(arr[l] > arr[r]) {
                swap(arr, more - 1, l);
                more--;

            } else {
                l++;
            }
        }
        swap(arr, more, r);
        return new int[]{less + 1,more};
    }

    public static void swap(int[] arr, int p1, int p2) {
        int t = arr[p1];
        arr[p1] = arr[p2];
        arr[p2] = t;
    }

    public static void quickSort(int[] arr, int l, int r) {
            if (l < r) {
                swap(arr, l + (int)((Math.random()) * (r - l + 1)), r);
                int[] p = partition(arr, l, r);
                quickSort(arr, l, p[0] - 1);
                quickSort(arr, p[1] + 1, r);
            }
    }

    public static void quickSort(int[] arr)
    {
        quickSort(arr, 0, arr.length - 1);
    }

    public static void main(String[] args) {
        int[] arr = {1,5,7,6,2,5,10,11,5,9,11};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }

     */




    //逆序对
    /*
     public int merge(int[] nums, int l, int mid, int r) {
        int p1 = l, p2 = mid + 1, res = 0, i = 0;
        int[] help = new int[r - l + 1];
        while ((p1 <= mid) && (p2 <= r)) {
            res += nums[p1] > nums[p2] ? (mid - p1 + 1) : 0;
            help[i++] = nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++];
        }
        while (p1 <= mid) {
            help[i++] = nums[p1++];
        }
        while (p2 <= r) {
            help[i++] = nums[p2++];
        }

        for (i = 0;i < help.length;i++) {
            nums[l + i] = help[i];
        }
        return res;
}

    public int process(int[] nums, int l, int r) {
        if (l == r) {
            return 0;
        }
        int mid = l + ((r - l) >>> 1);
        return process(nums, l, mid) +
        process(nums, mid + 1, r) +
        merge(nums, l , mid, r);
    }

    public int reversePairs(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        int ret = process(nums, 0, nums.length - 1);
        return ret;
    }

    */


    //lc ：2104
    /*
        public long subArrayRanges(int[] nums) {
        int n = nums.length;
        long ret = 0;
        for (int i = 0; i < n; i++) {
            int minVal = Integer.MAX_VALUE, maxVal = Integer.MIN_VALUE;
            for (int j = i; j < n; j++) {
                minVal = Math.min(minVal, nums[j]);
                maxVal = Math.max(maxVal, nums[j]);
                ret += maxVal - minVal;
            }
        }
        return ret;
    }
     */
}
